package com.gxc.linkedList;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 滑动窗口
 * 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次 向右边滑一个位置。
 * 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
 * [4 3 5] 4 3 3 6 7
 * 4 [3 5 4] 3 3 6 7
 * 4 3 [5 4 3] 3 6 7
 * 4 3 5 [4 3 3] 6 7
 * 4 3 5 4 [3 3 6] 7
 * 4 3 5 4 3 [3 6 7]
 * 窗口中最大值为5 窗口中最大值为5 窗口中最大值为5窗中最大值为4 窗中最大值为6
 * 窗口中最大值为7
 * 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
 * 请实现一个函数。
 * 输入:
 * 整型数组arr，窗口头小为w。
 * 输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的 以本题为例，结果应该返回[5,5,5,4,6,7]。
 */
public class SlidingWindow {

    public static void main(String[] args) {
        //int[] array = new int[]{4,3,5,4,3,3,6,7};

        int[] array = new int[]{6,3,5,4};

        int[] maxArray = slidingWindow(array, 3);

        for (int i = 0; i < maxArray.length; i++) {
            System.out.println(maxArray[i]);
        }

        System.out.println("----------");

        maxArray = slidingWindowUseLinkList(array, 3);
        for (int i = 0; i < maxArray.length; i++) {
            System.out.println(maxArray[i]);
        }
    }

    /**
     * 不使用额外的变量循环
     * 数组记录下标，比记录值，记录的信息更多
     * @param array 数组
     * @param w   窗口大小
     * @return
     */
    private static int[] slidingWindowUseLinkList(int[] array, int w) {
        int[] maxArray = new int[array.length-w+1];

        LinkedList<Integer> queue = new LinkedList();
        //窗口左边界
        int l = 0;
        for (int i = 0; i < array.length; i++) {
            //如果队列不为空，则队列后续比较大小，保持队列单向
            while (!queue.isEmpty() && array[queue.peekLast()] <= array[i]) {
                queue.pollLast();
            }

            queue.addLast(i);

            //如果当前的i - 队列中第一个数的 i 等于窗口的大小,则弹出队列第一个，将过期的元素弹出
            //队列首的元素肯定是先加入的元素，保持队列首元素i和现有i 小于等于窗口，肯定不会越界
            if (i- queue.peekFirst()== w) {
                queue.pollFirst();
            }
            //窗口前几个数累计进入队列，第w -1 进入后，即可得出该窗口的最大数就是队列首
            if (i >= w -1) maxArray[l++] = array[queue.peekFirst()];
        }
        return maxArray;
    }

    /**
     *
     * @param array  数组
     * @param w  窗口大小
     * @return
     */
    private static int[] slidingWindow(int[] array, int w) {
        int[] maxArray = new int[array.length-w+1];
        //大根堆
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        int l = 0;
        int r = 0;
        while (r<array.length) {
            //右边界先滑动窗口大小的位置
            while (r-l<3) {
                if (queue.isEmpty()) {
                    queue.add(array[r]);
                } else {
                    //如果队列内最大值小于新加入的值，则清空队列后，新加入的值加入队列
                    if (queue.peek()<array[r]) {
                        while (!queue.isEmpty()) {
                            queue.poll();
                        }
                        queue.add(array[r]);
                    } else {
                        queue.add(array[r]);
                    }
                }
                r++;
            }
            maxArray[l] = queue.peek();
            if (array[l] == queue.peek()) {
                queue.poll();
            }
            l++;
        }
        return maxArray;
    }

}
